MOD = 10 ** 9 + 7


class Solution:
    def waysToDistribute(self, n: int, k: int) -> int:
        # dp[i][j] 将i个糖果放进j个袋子的方案数
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        for j in range(1, k + 1):
            dp[j][j] = 1
            for i in range(j + 1, n + 1):
                dp[i][j] = (dp[i - 1][j] * j + dp[i - 1][j - 1]) % MOD

        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().waysToDistribute(3, 2))  # 3
    print(Solution().waysToDistribute(4, 2))  # 6
    print(Solution().waysToDistribute(20, 5))  # 206085257
